\section{Introduction}

% What is BFS for planning
One of the most successful approaches to planning is best-first search. 
Best-first search typically employs a heuristic function that maps any state to 
a real number that estimates the distance to goal.
At the beginning of search, 
the initial state $s_{0}$ is inserted 
into an $open$ list. At each step 
of the best-first search, a state with the smallest heuristic value is 
fetched from $open$ to check if it is a goal state. If not, all of its successors are then 
inserted into the open list again for later exploration. 

%	1. current problem with best-first search: exponentially large search space.
The number of states expanded by 
best-first search
depends largely on the quality of the heuristic function. 
Best-first search with a perfect heuristic function only needs
to expand $O(|L|)$ states where $L$ is % cite AIMA
the solution path from the initial state to a goal state~\cite{aima}. 
On the other hand, best-first search for planning with almost perfect heuristic 
may still explore an exponential number of states before finding a goal~\cite{Helmert08}. 
In practice, since the length of the solution path $L$ is much smaller
than the number of expanded states, it is easy to see
that most of the states explored by 
a best-first search are not on the solution path. 

% 	2. why there are plateaus 
During the best-first search, for any state $s$ explored,  
we define the incumbent heuristic value $h^{*}(s)$ 
as the smallest heuristic function value of all states 
explored so far till $s$. Evidently, $h^{*}$ decreases monotonically 
during search and finally reaches $0$ when a goal is found. 

For a given planning problem, let $\mathcal{S}$ be the set of all generated states, since 
we have $|\mathcal{S} | \gg h^{*}(s_{0})$, and $h^{*}(s)$ 
is a monotonic mapping from $\mathcal{S}$ to $[0, h^{*}(s_{0}) ]$, 
we see that for most of the state pairs $(s, s')$ 
where $s'$ is explored right after $s$ during the search, $h^{*}(s) = h^{*}(s')$.

% 	3. Why it is important to jump out of plateau
The reasoning above shows that most of the time
a best-first search for planning explores states
without reducing $h^{*}$. 
This phenomenon is named {\em plateau exploration} as it involves
state exploration without changing $h^{*}$. 
Therefore,  to improve the performance of best-first search for planning,
it is important to find a way that can reduce plateau exploration. 

% Motivation: why do we use random walk
In this paper, we propose to use random walks to assist best-first search for planning 
to escape from plateau more quickly. Specifically, when the best-first search 
makes no progress on $h^{*}$ for an extended period, we use 
a random walk algorithm
to explore the search space and help 
escape from the plateau. 

There are three advantages
of using random walks to assist best-first search for planning. 
First, a random walk 
has the potential to directly and quickly jump out of a local minima
region where it is not likely to find an ``exit'' state that reduces
$h^{*}$, whereas a best-first search will have to explore 
all possible states around the local minima. 
Second, comparing to best-first search in which 
heuristic functions are evaluated at each state, 
the random walk algorithm can skip heuristic evaluations 
of most of the intermediate states during exploration, 
making space exploration more efficient. 
Third, random walks require little memory, and therefore 
do not add space complexity to the original 
best-first search. 

% Contributions of this paper
We make three contributions in this paper. 
First, we propose an algorithmic framework 
where random walks are incorporated 
to help best-first search find exit states
of a plateau. Second, we conduct theoretical analysis to 
study the impact of using random walks on different 
types of search space models, including tree search, 
graph search, and search with many dead end states. 
Third, we implement two variants of the proposed algorithm 
and compare their performances to a pure 
best-first search planner on various testing domains. 

\nop{
Experimental results 
on IPC6 domains demonstrate both the efficiency of our proposed algorithm 
and the soundness of our theoretical analysis. 
}